package com.zfl;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

public class CalcEquation {

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String,Map<String,Double>> graph = new HashMap<>();

        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0);
            String b = equations.get(i).get(1);

            double value = values[i];

            graph.computeIfAbsent(a,k->new HashMap<>()).put(b,value);
            graph.computeIfAbsent(b,k->new HashMap<>()).put(a,1.0/value);
        }

        int n = queries.size();
        double[] res = new double[n];

        for (int i=0;i<n;i++) {
            List<String> query = queries.get(i);
            String a = query.get(0);
            String b = query.get(1);

            if (!graph.containsKey(a)||!graph.containsKey(b)) {
                res[i] = -1.0;
                continue;
            }

            HashSet<String> visited = new HashSet<>();
            res[i] = dfs(graph,visited,a,b,1.0);
        }
        return res;
    }

    private double dfs(Map<String, Map<String, Double>> graph, HashSet<String> visited, String current, String target, double currentProduct) {
        visited.add(current);

        if (current.equals(target)) {
            return currentProduct;
        }

        for (Map.Entry<String, Double> entry : graph.get(current).entrySet()) {
            if(!visited.contains(entry.getKey())) {
                double res = dfs(graph,visited,entry.getKey(),target,currentProduct*entry.getValue());
                if (res!=-1.0) {
                    return res;
                }
            }
        }
        return -1.0;
    }
}
